/**
 * 剑指 Offer 13. 机器人的运动范围
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 */

let sumOfDigitsCache;

/**
 * @param {number} num
 * @return {number}
 */
function sumOfDigits(num) {
  if (sumOfDigitsCache[num] >= 0) {
    return sumOfDigitsCache[num];
  }
  let n = num;
  let sum = 0;
  while (n > 0) {
    sum += (n % 10);
    n = Math.floor(n / 10);
  }
  sumOfDigitsCache[num] = sum;
  return sum;
}

let count;

/**
 * @param {boolean[][]} sign
 * @param {number} i
 * @param {number} j
 * @param {number} k
 */
function move(sign, i, j, k) {
  if (i < 0 || j < 0) {
    return;
  }
  const { length: m } = sign;
  const { length: n } = sign[0];
  if (i >= m || j >= n || sign[i][j] || (sumOfDigits(i) + sumOfDigits(j)) > k) {
    return;
  }
  sign[i][j] = true;
  count += 1;
  move(sign, i + 1, j, k);
  move(sign, i, j + 1, k);
  move(sign, i - 1, j, k);
  move(sign, i, j - 1, k);
}

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
function movingCount(m, n, k) {
  sumOfDigitsCache = new Array(Math.max(m, n)).fill(-1);
  const sign = new Array(m);
  for (let i = 0; i < m; i += 1) {
    sign[i] = new Array(n).fill(false);
  }
  sign[0][0] = true;
  count = 1;
  move(sign, 0, 1, k);
  move(sign, 1, 0, k);
  return count;
}

console.log(movingCount(2, 3, 1) === 3);
console.log(movingCount(3, 1, 0) === 1);
